package priv.conceit.study.leetcode.simple.official;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 编号14
 * longest-common-prefix 最长公共前缀
 * <a href="https://leetcode-cn.com/problems/longest-common-prefix/"></a>
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串 ""。
 * <p>
 * 示例 1:
 * 输入: ["flower","flow","flight"]
 * 输出: "fl"
 * <p>
 * 示例 2:
 * 输入: ["dog","racecar","car"]
 * 输出: ""
 * 解释: 输入不存在公共前缀。
 *
 * @author Conceit
 * @since 1.0.0, 2019/7/4
 */
@SuppressWarnings("ALL")
public class LongestCommonPrefix {

	/**
	 * 使用前缀树 完成
	 * <p>
	 * 新增公共字符数组
	 * 查询该前缀树结构每一个层级
	 * <p>
	 * 如果第一个层级为空则直接返回
	 * <p>
	 * 不为空则检查该目录是否只包含一个节点且不为空
	 * <p>
	 * 不为空且只有一个节点 则检查该节点是否为最终节点
	 * <p>
	 * 是则为公共前缀
	 * 不是则继续向下遍历
	 * 依次循环
	 *
	 * @param args
	 */
	public static void main(String[] args) {
//		String[] strings = new String[]{"flower", "flow", "flight"};
//		String[] strings = new String[]{"flower", "flow", "flight"};
		String[] strings = new String[]{"flower","flow","flight"};
		String result=new LongestCommonPrefix().longestCommonPrefix(strings);
		System.out.println(result);
	}


	/**
	 * 过滤[] [""]
	 * 数组长度只有1的元素直接返回
	 * @param strs
	 * @return
	 */
	public String longestCommonPrefix(String[] strs) {
		if(strs==null||strs.length==0){
			return "";
		}
		if(Arrays.asList(strs).stream().anyMatch(x->x.equals(""))){
			return "";
		}

		Trie trie=new Trie();
		for (String str:strs){
			trie.insert(str);
		}
		return trie.searchLongestCommonPrefix();
	}

	public static class Trie {


		/**
		 * 小写字母 a-z共26位
		 */
		public static int dictSize = 26;
		public TrieNode root;

		/**
		 * 初始化时 便捎带初始化一个空的node
		 */
		public Trie() {
			root = new TrieNode(' ');
		}


		/**
		 * 新增
		 * 每个子目录下一行的arr[]位26
		 * 用arr[diff]就可以获取到指定node上是否包含字符
		 * <p>
		 * 从root节点开始执行 如找到指定字符 则将root指向子节点
		 *
		 * @param word
		 */
		public void insert(String word) {

			TrieNode curNode = root;
			for (int i = 0; i < word.length(); i++) {
				int diff = word.charAt(i) - 'a';
				if (curNode.childs[diff] == null) {
					curNode.childs[diff] = new TrieNode(word.charAt(i));
				}
				curNode = curNode.childs[diff];
			}
			curNode.isLast = Boolean.TRUE;

		}

		public String searchLongestCommonPrefix() {
			String result = "";
			TrieNode curNode = root;
			while (true) {

				if (curNode.childs == null) {
					break;
				}
				List<TrieNode> trieNodeList = Arrays.asList(curNode.childs).stream().filter(x -> x != null).collect(Collectors.toList());
				if (trieNodeList.size() > 1||trieNodeList.size()==0) {
					break;
				} else {
					curNode = trieNodeList.stream().findFirst().get();
					if (curNode.isLast) {
						return result + curNode.value;
					} else {
						result = result + curNode.value;
					}
				}
			}

			return result;
		}

		/**
		 * TrieNode为节点
		 */
		private class TrieNode {
			/**
			 * 初始化方法
			 *
			 * @param value
			 */
			public TrieNode(char value) {
				this(new TrieNode[Trie.dictSize], value, Boolean.FALSE);
			}

			public TrieNode(TrieNode[] childs, char value, boolean isLast) {
				this.childs = childs;
				this.isLast = isLast;
				this.value = value;
			}

			/**
			 * 下属的子孙节点
			 */
			private TrieNode[] childs;
			/**
			 * 是否为最后一个节点
			 */
			private boolean isLast;
			/**
			 * 当前的字符
			 */
			private char value;


		}
	}

}
